/*
 * @lc app=leetcode.cn id=330 lang=golang
 *
 * [330] 按要求补齐数组
 */

// @lc code=start

// 如果数字 n 可以被数组内表示，且n在数组中
// 那么 2n 也可以被数组内表示
// 从 1 开始遍历，获取当前数组中数字的和，直到和大于等于目标值
// 已经超出了目前数组索引，或数组中数字大于前缀和
func minPatches(nums []int, n int) int {
	count := 0
	index := 0
	cur := 1
	m := len(nums)
	for cur <= n {
		if index >= m || nums[index] > cur {
			count++
			cur *= 2
		} else {
			cur += nums[index]
			index++
		}
	}
	return count
}

// @lc code=end
